package com.study.common.tree;

/**
 * @author yaojinshan
 * @version 1.0
 * @description: Btree 实现类 == 二叉搜索树要求
 * 参考：https://www.cnblogs.com/ysocean/p/8032642.html
 * 规则：1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 *      2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 * 它的左、右子树也分别为二叉排序树。
 * @date 2019/7/22 16:29
 */
@SuppressWarnings("all")
public class Btree implements TreeInterface {
    //树的根节点
    private Node rootNode;

    public Btree() {

    }

    public Node getRootNode() {
        return rootNode;
    }

    public void setRootNode(Node rootNode) {
        this.rootNode = rootNode;
    }

    @Override
    public Node find(int key) {
        return null;
    }

    @Override
    public boolean insert(int data) {
        Node newNode = new Node(data);
        if(this.rootNode == null){
            setRootNode(newNode);
        }else{

            Node currentNode = getRootNode(); //从根节点开始操作
            while (currentNode != null){
                //如果当前节点的值  大与新插入的节点值  则搜索当前节点的 左子节点
                if (currentNode.getNodeValue() > newNode.getNodeValue()){
                    //如果当前节点的左节点为null 则直接入将新节点作为当前节点的左子节点
                    if(currentNode.getLeftChild() == null){
                        currentNode.setLeftChild(newNode);
                        return true;
                    }else{
                        //如果当前节点的左子节点不为null 则改变当前节点为左子节点 递归下一次循环
                        currentNode = currentNode.getLeftChild();
                    }
                }else{
                    //如果当前节点的值 小与新插入的节点值  则搜索当前节点的 右子节点
                    //如果当前节点的右节点为null 则直接入将新节点作为当前节点的右子节点
                    if(currentNode.getRightChild() == null){
                        currentNode.setRightChild(newNode);
                        return true;
                    }else{
                        //如果当前节点的右子节点不为null 则改变当前节点为右子节点 递归下一次循环
                        currentNode = currentNode.getRightChild();
                    }
                }
            }
        }
        return false;
    }

    @Override
    public void infixOrder(Node current) {
        if (current != null){
            infixOrder(current.getLeftChild());
            System.out.print(current.getNodeValue() + " ");
            infixOrder(current.getRightChild());
        }
    }

    @Override
    public void preOrder(Node current) {
        if (current != null){
            System.out.print(current.getNodeValue() + " ");
            preOrder(current.getLeftChild());
            preOrder(current.getRightChild());
        }
    }

    @Override
    public void postOrder(Node current) {
        if (current != null){
            postOrder(current.getLeftChild());
            postOrder(current.getRightChild());
            System.out.print(current.getNodeValue() + " ");
        }
    }

    @Override
    public Node findMax() {
        //找当前树的最大节点  只需要找最右节点
        Node currentNode = rootNode;
        while(currentNode.getRightChild() != null){
            currentNode = currentNode.getRightChild();
        }
        return currentNode;
    }

    @Override
    public Node findMin() {
        //找当前树的最大节点  只需要找最左节点
        Node currentNode = rootNode;
        while(currentNode.getLeftChild() != null){
            currentNode = currentNode.getLeftChild();
        }
        return currentNode;
    }

    @Override
    public boolean delete(int deleteNodeValue) {
        //从根节点开始遍历 如果存在这个值
        return false;
    }
}
